// https://leetcode.cn/problems/validate-binary-search-tree/

// 算法思路总结：
// 1. 中序遍历验证二叉搜索树
// 2. 利用BST中序遍历有序的特性
// 3. 维护前驱节点值，比较当前节点值是否严格递增
// 4. 递归检查左右子树是否都满足BST性质
// 5. 时间复杂度：O(n)，空间复杂度：O(h)（递归栈深度）

#include <iostream>
using namespace std;

#include <climits>
#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    long long prev = LLONG_MIN;
    bool isValidBST(TreeNode* root) 
    {
        if (root == nullptr) return true;

        bool left = isValidBST(root->left);

        if (root->val > prev)
            prev = root->val;
        else return false;

        bool right = isValidBST(root->right);

        return left && right;
    }
};

int main()
{
    vector<string> tree1 = {"2", "1", "3"};
    vector<string> tree2 = {"5", "1", "4", "null", "null", "3", "6"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.isValidBST(root1) << endl;
    cout << sol.isValidBST(root2) << endl;

    return 0;
}